import time


class Solution2:
    def maxNumber(self, nums1: list, nums2: list, k: int) -> list:
        """貌似还没上面一个快"""
        len1, len2 = len(nums1), len(nums2)
        res_list = []
        for i in range(max(k - len2, 0), min(len1 + 1, k + 1)):
            list1 = [10]
            list2 = [10]
            for j1 in range(0, len1):
                while nums1[j1] > list1[-1] and len1 - j1 - 1 >= i + 1 - len(list1):
                    list1.pop(-1)
                if len(list1) < i + 1:
                    list1.append(nums1[j1])
            for j2 in range(0, len2):
                while nums2[j2] > list2[-1] and len2 - j2 - 1 > k - i - len(list2):
                    list2.pop(-1)
                if len(list2) <= k - i:
                    list2.append(nums2[j2])
            j1, j2 = 1, 1
            while j1 <= i:
                if j2 < len(list2):
                    if list1[j1] > list2[j2]:
                        list2.insert(j2, list1[j1])
                        j1 += 1
                    elif list1[j1] == list2[j2]:
                        for h in range(1, min(len(list1) - j1, len(list2) - j2)):
                            if list1[j1 + h] > list2[j2 + h]:
                                list2.insert(j2, list1[j1])
                                j1 += 1
                                break
                            elif list1[j1 + h] < list2[j2 + h]:
                                break
                        else:
                            if len(list1) - j1 > len(list2) - j2:
                                list2.insert(j2, list1[j1])
                                j1 += 1
                    j2 += 1
                else:
                    list2.extend(list1[j1:])
                    print("maxres")
                    break
            res_list.append(list2)
        res_list.sort()
        return res_list[-1][1:]


class Solution:
    def maxNumber(self, nums1: list, nums2: list, k: int) -> list:
        len1, len2 = len(nums1), len(nums2)
        res = [10]
        i_list = range(max(k - len2, 0), min(len1 + 1, k + 1))
        for i in i_list:
            list1 = [10]
            list2 = [10]
            for j1 in range(0, len1):
                while nums1[j1] > list1[-1] and len1 - j1 - 1 >= i + 1 - len(list1):
                    list1.pop(-1)
                if len(list1) < i + 1:
                    list1.append(nums1[j1])
            for j2 in range(0, len2):
                while nums2[j2] > list2[-1] and len2 - j2 - 1 > k - i - len(list2):
                    list2.pop(-1)
                if len(list2) <= k - i:
                    list2.append(nums2[j2])
            j1, j2 = 1, 1
            while j1 <= i:
                if j2 < len(list2):
                    if list1[j1] > list2[j2]:
                        list2.insert(j2, list1[j1])
                        j1 += 1
                    elif list1[j1] == list2[j2]:
                        mid1 = list1[j1:]
                        mid2 = list2[j2:]
                        if mid1 > mid2:
                            list2.insert(j2, list1[j1])
                            j1 += 1
                    j2 += 1
                else:
                    list2.extend(list1[j1:])
                    break
            res = max(res, list2)
        return res[1:]


class Solution3:
    def maxNumber(self, nums1: list, nums2: list, k: int) -> list:
        from collections import deque
        len1, len2 = len(nums1), len(nums2)
        res = []
        i_list = range(max(k - len2, 0), min(len1 + 1, k + 1))
        for i in i_list:
            list1 = deque([10])
            list2 = deque([10])
            count1, count2 = 1, 1
            for j1 in range(0, len1):
                while nums1[j1] > list1[-1] and len1 - j1 - 1 >= i + 1 - count1:
                    list1.pop()
                    count1 -= 1
                if len(list1) < i + 1:
                    list1.append(nums1[j1])
                    count1 += 1
            for j2 in range(0, len2):
                while nums2[j2] > list2[-1] and len2 - j2 - 1 > k - i - count2:
                    list2.pop()
                    count2 -= 1
                if len(list2) <= k - i:
                    list2.append(nums2[j2])
                    count2 += 1
            list1.popleft()
            list2.popleft()
            mid_res = []
            while list1 or list2:
                tar_list = list1 if list1 > list2 else list2
                mid_res.append(tar_list.popleft())
            res = max(res, mid_res)
        return res


a = Solution3()
now = time.time()
print(a.maxNumber(nums1=[3, 4, 6, 5], nums2=[9, 1, 2, 5, 8, 3], k=5))
print(a.maxNumber(nums1=[6, 7], nums2=[6, 0, 4], k=5))
print(a.maxNumber(nums1=[3, 9], nums2=[8, 9], k=3))
print(a.maxNumber(nums1=[5, 1, 0], nums2=[5, 2, 1], k=3))
print(a.maxNumber(nums1=[5, 5, 5, 1, 0], nums2=[5, 2, 1], k=5))
print(a.maxNumber([2, 5, 6, 4, 4, 0], [7, 3, 8, 0, 6, 5, 7, 6, 2], 15))
print(a.maxNumber([1, 6, 5, 4, 7, 3, 9, 5, 3, 7, 8, 4, 1, 1, 4], [4, 3, 1, 3, 5, 9], 21))
# [4, 3, 1, 6, 5, 4, 7, 3, 9, 5, 3, 7, 8, 4, 1, 3, 5, 9, 1, 1, 4]
print(a.maxNumber([5, 4, 3, 2], [5, 4, 3, 2, 1], 9))
print(a.maxNumber([1, 2, 3, 4], [1, 2, 3, 4, 5], 9))
print(a.maxNumber([1, 2, 3, 4, 5], [1, 2, 3, 4], 9))
print(a.maxNumber(
    [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
     1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
     1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
    [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
     1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
     1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1], 100))
print(a.maxNumber([1, 1, 1, 1, 1, 1], [1, 1, 1, 1, 1, 1], 4))
print(a.maxNumber([1, 2], [], 2))
print(a.maxNumber(
    [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
     1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
     1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
     1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
     1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
     1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2,
     2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
     2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
     2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2],
    [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
     1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
     1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
     1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
     1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
     1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2,
     2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
     2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
     2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2],
    200))
print(time.time() - now)
